#define _CRT_SECURE_NO_WARNINGS

class Solution {
public:
    void getNext(string& needle, vector<int>& next)
    {
        next[0] = -1;
        int i = 0, j = -1;
        while (i < needle.size() - 1)
        {
            if (j == -1 || needle[i] == needle[j]) {
                next[++i] = ++j;
            }
            else
            {
                j = next[j];
            }
        }
    }

    int getTarget(string& haystack, string& needle, vector<int>& next)
    {
        int i = 0, j = 0;
        while (i < haystack.size())
        {
            if (haystack[i] == needle[j])
            {
                if (j == needle.size() - 1)
                    return i - j;
                i++;
                j++;
            }
            else if (j == 0)
            {
                i++;
            }
            else
                j = next[j];
        }
        return -1;
    }

    int strStr(string haystack, string needle) {
        vector<int> next(needle.size(), 0);
        getNext(needle, next);
        return getTarget(haystack, needle, next);
    }
};

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string tmp(s.begin() + 1, s.end());
        tmp += s;
        tmp.erase(tmp.size() - 1);
        cout << tmp;
        if (tmp.find(s) == string::npos)
            return false;
        return true;
    }
};